This invention relates generally to analog-to-digital conversion methods and to methods of performing electronic multiplication. More specifically, the present invention provides a method of performing analog-to-digital conversion simultaneously with multiplication. The invention is particularly well suited for use in data compression of a large number of parallel analog signals. In addition, the present disclosure teaches an architecture for performing a separable transform on a 2-dimensional imaging sensor array.
Imaging sensor arrays such as charge coupled devices (CCDs) or photodiode arrays are commonly used in imaging applications such as machine vision or digital cameras. Such imaging arrays typically comprise 500,000 to 1,000,000 microscopic light sensors arranged on the surface of the imaging chip. Each sensor generates an analog value (e.g., voltage) which is a function of the incident light intensity. For an image to be stored, it is generally necessary to digitize the analog value from each sensor.
Digitization is typically performed with a high speed analog-to-digital converter (ADC) which sequentially digitizes the analog signal from each sensor. The large number of sensors in an imaging array results in a large amount of data being produced by each image acquired. Therefore, for most imaging devices, some kind of data compression scheme is employed to make the digitized image easier to store and transmit.
Separable 2-D transforms are commonly used for data compression because they are relatively easy to implement (because they are xe2x80x98separablexe2x80x99). JPEG and MPEG are examples of image data compression techniques that use separable 2-D transforms. FIG. 1 shows an 8xc3x978 pixel array and illustrates some of the basic concepts involved in a separable 2-D transform. In a separable 2-D transform, the digital values from each row and each column are multiplied by a precomputed digital coefficient (R1, R2, . . . R8; C1, C2, . . . C8). In this way, each pixel value is multiplied by a number RiCj, where i and j are integers between 1 and 8. The computation and use of separable 2-D transforms is well known in the art of signal processing. There exist many different kinds of separable 2-D transforms. Many data compression techniques, including separable 2-D transforms, require a large number of arithmetic multiplications to be performed, due to the large number of digitized pixel values. It is noted that the 8xc3x978 pixel array of FIG. 1 is typically only a small block in a larger pixel array having many thousands of pixels.
The current approach to performing these multiplications (for example, in a digital camera) is to output the digital pixel values to a dedicated digital signal processor to perform the digital multiplications. This can be a problem because it requires a relatively expensive processing chip and consumes a lot of power.
An alternative approach suggested in the literature performs multiplication directly on the analog values before digitization, followed by variable step size quantization (digitization). This approach is undesirable because it requires analog memory and sophisticated analog processing which requires large silicon area and power and can be complex to implement. For more information, reference can be made to xe2x80x9cA Compressed Digital Output CMOS Image Sensor with Analog 2-D Discrete Cosine Transform Processors and ADC/Quantizerxe2x80x9d, by S. Kawahito et al. ISSCC Digest of Technical Papers, San Francisco, Calif., February 1997.
U.S. Pat. No. 5,801,657 to Fowler et al. discloses a method and apparatus for performing analog-to-digital conversion (ADC) at the pixel level. In other words, each pixel is provided with a simple ADC. Each ADC receives inquiry signals from a driving circuit outside the sensor array. Only one driving circuit is needed for the entire array. The digital pixel values are outputted serially. The method is called Multi-Channel Bit Serial (MCBS) Analog-to-digital Conversion. A single channel version of MCBS is termed a Bit Serial ADC. An MCBS ADC has many advantages applicable to image acquisition, but it does not provide digital multiplication. If a separable 2-D transform is to be performed on an MCBS-digitized image, an additional digital signal processor is required. This increases the cost and power consumption of an imaging device.
Therefore, it would be desirable to be able to perform multiplication on a series of digitized values without needing a separate digital signal processor.
Also, since MCBS ADCs have many advantages, it would be desirable to perform multiplication using the MCBS hardware and method previously disclosed.
FIG. 2 shows a single channel bit serial ADC according to U.S. Pat. No. 5,801,657 to Fowler et al.
A single channel bit serial ADC comprises a comparator 20 and a one-bit latch 22. An output 32 of the comparator is connected to the latch gate input 34. A monotonicaly increasing stairstep RAMP signal 24 enters a comparator inverting input 30 and an analog value (a voltage) 28 to be digitized enters a comparator noninverting input 26. Therefore, when the RAMP 24 exceeds the analog voltage 28, output 32 of the comparator goes low. The comparator output enters a gate 34 of the latch 22. BITX 36 enters data input 38 of latch 22. Therefore, when the RAMP signal exceeds the analog voltage 28, the latch 22 latches the BITX value. The latched BITX value is provided at the serial digital output.
FIG. 3 is a diagram illustrating the interaction between RAMP and BITX signals. RAMP 24 is a staircase waveform with predetermined voltage levels 40 and voltage steps 46. BITX is a squarewave. BITX has transitions 42 that are timed so that there is a delay 44 between the BITX transition 42 and RAMP voltage steps 46. The delay 44 provides the latch with a set-up time before the comparator changes states.
RAMP and BITX are designed together such that desired digital values (0 or 1) are associated with predetermined analog voltage ranges, shown as A-B, B-C, C-D, D-E, and E-F. The voltage ranges are determined by the voltage steps 46 of the RAMP signal.
FIG. 4 shows a quantization table for the RAMP and BITX signals of FIG. 3. The digital output associated with the voltage ranges is changed by changing BITX.
The bit serial ADC technique can be used to digitize analog values to multiple bits of precision. The bits are output serially. The bits can be output in any order desired: the most significant bit (MSB) can come first, or the least significant bit (LSB) can come first, for example. A distinct RAMP waveform is required for each bit of precision. The data is output from the latch output between each RAMP waveform. The voltage levels 40 of RAMP and the pattern of BITX can be changed to output any desired quantization table. For example, gray code can be output by appropriately designing BITX and RAMP.
One of the great advantages of bit serial ADCs is that many separate ADCs can be operated in parallel to form a Multi-Channel Bit Serial (MCBS) ADC. This is shown in FIG. 5. The circuitry that generates RAMP and BITX delivers the same RAMP and BITX to all the ADCs 48. Since the hardware for each ADC is so simple, many ADCs (e.g., thousands) can operate in parallel. This feature makes the MCBS ADC particularly useful in applications where a large number of analog values must be digitized. This situation arises, for example, in the digitization of analog signals from an image sensor. In an image sensor, a single ADC can be provided for each pixel, or small group of pixels.
Accordingly, it is a primary object of the present invention to provide a method of performing digital multiplication that:
1) is fully compatible with the Multi-Channel Bit Serial analog-to-digital conversion method and hardware,
2) requires no additional hardware to be added to the existing MCBS circuitry,
3) can be used to multiply each digitized value by 2 independently adjustable coefficients,
4) can be programmed to multiply by an accurately determined coefficient,
5) can be used to perform separable 2-D transforms, convolution, and filtering for image data compression,
6) can be used in any situation where a large number of parallel analog signals are to be digitized and multiplied by a coefficient, and
7) can be used in any situation where both analog-to-digital conversion and digital multiplication are performed;
It is also an object of the present invention to provide a method for performing simultaneous analog-to-digital conversion and multiplication in a single slope analog-to-digital converter.
These and other objects and advantages will be apparent upon reading the following description and accompanying drawings.
The above objects and advantages are attained by altering the RAMP and BITX signals supplied to a bit serial ADC. Altering the RAMP signal can result in multiplication of the digital output by a coefficient, and altering the BITX signal can result in multiplication of the digital output by a second coefficient.
M-RAMP and M-BITX are generic terms used to denote RAMP and BITX signals that provide multiplication.
There exists a 1-RAMP signal that provides no multiplication. Multiplication by a factor of X using RAMP is accomplished by generating a M-RAMP signal having voltage levels different by a factor of 1/X than voltage levels of the 1-RAMP signal. The M-RAMP signal is then applied to a comparator input of a bit serial ADC.
There exists a 1-BITX signal with frequency F0 that provides no multiplication. In providing multiplication via BITX, a M-BITX signal is produced having an average frequency close to XF0. The M-BITX signal comprises alternating segments of frequency KF0/N and frequency KF0/N+1, where N is a positive integer, and wherein K is an integer. The M-BITX signal is then applied to a data input of a bit serial ADC. In cases where Kxe2x89xa01, the RAMP signal must be altered as well.
Preferably, K=2D, where D is a number of binary bits used to represent a fractional part of 1/X. Preferably, N is selected so that Nxe2x89xa6(K/X) less than N+1.
Also preferably, the average frequency of M-BITX is close to XF0. For example, the average frequency of M-BITX is preferably equal to XF0 to within a factor of 1/2n, where n is a number of bits of resolution desired for analog-to-digital conversion. Alternatively, the average frequency of M-BITX can be within 10% or 5% of XF0.
The present invention also includes a method for generating M-RAMP having a xe2x80x98snap to gridxe2x80x99 characteristic. The method begins with selecting N, A, and B according to the relation:       N    +          A      B        ≈            K      X        .  
N and K are integers. K is a grid density factor. Value A is added to a first running sum at a frequency of 2KF0. The first running sum can be generated in an accumulator. Value A digital number is produced having value N if the running sum does not roll over a value B after A is added. The digital number has value N+1 if the running sum rolls over the value B after A is added. The series of digital numbers produced are added to a second running sum at a rate of 2KF0. The second running sum is sent to a digital to analog converter (DAC). The output of the DAC is the desired M-RAMP signal. Preferably, N is selected such that Nxe2x89xa6(K/X) less than N+1 (i.e., N is preferably the integer part of K/X). Also preferably,   N  +      A    B  
is very close to the value K/X. The present invention includes algorithms for selecting N, A, and B.
The present invention also includes a similar method for generating M-BITX having a snap to grid characteristic. The method begins with selecting N, A, and B according to the relation:       N    +          A      B        ≈            K      X        .  
N and K are integers. K is the grid density factor. Value A is added to a running sum. The running sum can be generated in an accumulator, for example. Next a squarewave signal is generated having frequency KF0/N if the running sum does not roll over the value B after A is added. The squarewave signal has frequency KF0/(N+1) if the running sum does roll over the value B after A is added. Value A is added to the running sum after every edge transition in the squarewave signal. The squarewave signal is the desired M-BITX signal that provides multiplication by a factor of X. Preferably, N is selected such that Nxe2x89xa6(K/X) less than N+1 (i.e., N is preferably the integer part of K/X). Also preferably,   N  +      A    B  
is very close to the value K/X. The present invention includes algorithms for selecting N, A, and B.
The present invention also includes an apparatus for generating M-RAMP. The apparatus has a first accumulator for generating a first running sum. The first accumulator has a capacity B. The value A is added to the first running sum at a frequency of 2KF0. Values N, A and B are selected according to the relation:             N      +              A        B              ≈          K      X        ,
where N is an integer and K is the grid density factor. The apparatus also has a number selector. The number selector provides a digital number N when the running sum does not roll over the capacity B after A is added. The number selector provides a digital number N+1 when the running sum does roll over the capacity B after A is added. The number selector provides digital numbers at a frequency of 2KF0. The apparatus also has a second accumulator for adding the digital numbers to a second running sum. The apparatus further has a digital to analog converter (DAC) for converting the second running sum to an analog value. The analog values provided by the DAC comprise the desired M-RAMP signal that provides multiplication by a factor of X. The apparatus may include a clock for assuring that the accumulators and DAC operate at the correct frequencies.
The present invention also includes an apparatus for generating M-BITX with a snap to grid characteristic. The apparatus has an accumulator for adding the value A to a running sum within the accumulator. The accumulator has a capacity B. Values N, A and B are selected according to the relation       N    +          A      B        ≈      K    X  
where N is an integer, and K is the grid density factor. The apparatus also has a squarewave frequency generator in communication with the accumulator. The frequency generator generates frequency KF0/N when the running sum does not roll over the capacity B after A is added to the running sum. The frequency generator generates frequency KF0/(N+1) when the running sum does roll over the capacity B after A is added to the running sum. The accumulator adds A to the running sum after every transition edge of the squarewave frequency generator output. The frequency generator output is the desired M-BITX signal that provides multiplication by a factor of X. Preferably, the squarewave frequency generator comprises a clock providing frequency KF0 in communication with a frequency divider having a modulus selectable to be either N or N+1.
The present invention also includes an apparatus for acquiring an image and compressing/filtering the image. The apparatus has an array of photodetectors for producing analog signals. The photodetectors are arranged in rows and columns. The apparatus has bit serial analog-to-digital converters (ADCs) in communication with the photodetectors. The apparatus has M-RAMP generators for generating a number of different M-RAMP signals that provide multiplication by different coefficients. The apparatus has M-BITX generators for generating a number of different M-BITX signals that provide multiplication by different coefficients. The apparatus has circuitry for providing the different M-RAMP signals to the different columns, and for providing the different M-BITX signals to the different rows. The circuitry can, for example, comprise a switch matrix. The M-RAMP and M-BITX generators can comprise look-up tables storing information on the design of the different M-RAMP and M-BITX signals. Also, the M-RAMP and M-BITX generators can comprise fractional-N phase locked loops. It is understood that rows and columns in the present invention are interchangeable. Therefore, an apparatus with M-RAMP signals provided to the different rows, and M-BITX signals provided to the different columns is well within the scope of the claimed invention. It is also understood that rows and columns may be in a hexagonal array, or a radial array or pixels.
The present invention also includes a method for performing simultaneous A/D conversion and multiplication by a factor of X in a single slope ADC. The method has the step of changing the voltage/time slope of a single slope RAMP (SS-RAMP) signal used in the single slope ADC by a factor of 1/X.
The present invention also includes a second method for performing simultaneous A/D conversion and multiplication by a factor of X in a single slope ADC. The method has the step of changing the frequency of a single slope FREQ (SS-FREQ) signal used in the single slope ADC by a factor of X.
The present invention also includes a method for performing simultaneous analog-to-digital conversion and compression/filtering in an imaging photodetector array in communication with bit serial ADCs. Different M-BITX signals are provided to the different rows so that digital values from photodetectors in a given row are multiplied by the same coefficient. Different M-RAMP signals are provided to the different columns so that digital values from photodetectors in a given column are multiplied by the same coefficient. Therefore, each digital value from each photodetector in the array is multiplied by two coefficients determined by the location of the photodetector in the array. The method can be applied to small blocks in the array. The bit serial ADCs may be located on the photodetector array, or may be located on a separate chip.
The present invention also includes a method for performing simultaneous analog-to-digital conversion and compression/filtering in an imaging photodetector array in communication with single slope ADCs. Different multiplying SS-FREQ signals (M-SS-FREQ) are provided to the different rows so that digital values from photodetectors in a given row are multiplied by the same coefficient. Different multiplying SS-RAMP signals (M-SS-RAMP) are provided to the different columns so that digital values from photodetectors in a given column are multiplied by the same coefficient. Therefore, each digital value from each photodetector in the array is multiplied by two coefficients determined by the location of the photodetector in the array. The method can be applied to small blocks in the array. The single slope ADCs may be located on the photodetector array, or may be located on separate chip.